﻿// 0821train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode() = default;
    TreeNode(int val) : val(val) {};
};

TreeNode* BuildNode(vector<int>&tree_vec)
{
    TreeNode* root = new TreeNode(tree_vec[0]);
    int index = 1;
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);
    while (!bfs_queue.empty() && index<tree_vec.size())
    {
        TreeNode* node = bfs_queue.front();
        bfs_queue.pop();
        if (index<tree_vec.size() && tree_vec[index]!=INT_MIN)
        {
            node->left = new TreeNode(tree_vec[index]);
            bfs_queue.push(node->left);
        }
        index++;

        if (index<tree_vec.size() && tree_vec[index]!=INT_MIN)
        {
            node->right = new TreeNode(tree_vec[index]);
            bfs_queue.push(node->right);
        }
        index++;
    }
    return root;
}

class Solution01 {
public:
    int result = 0;
    int dfs(TreeNode* node)
    {
        if (node == nullptr) return 0;
        int left_node_count = dfs(node->left), right_node_count = dfs(node->right);
        int curr_left_count = 0, curr_right_count = 0;

        if (node->left && node->left->val == node->val)
        {
            curr_left_count = left_node_count + 1;
        }
        if (node->right && node->right->val == node->val)
        {
            curr_right_count = right_node_count + 1;
        }
        result = max(result, curr_left_count + curr_right_count);

        return max(curr_left_count, curr_right_count);
    }
    int longestUnivaluePath(TreeNode* root)
	{
        dfs(root);
        return result;
    }
};

/*
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
 
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
 */

class Solution02 {
public:
    int result = INT_MIN;
    int dfs(TreeNode* node)
    {
        if (node == nullptr) return 0;

        //舍弃负数
        int left_max = max(0, dfs(node->left));
        int right_max = max(0, dfs(node->right));

        int new_path = node->val + left_max + right_max;
        result = max(result, new_path);

        return max(node->val + left_max, node->val + right_max);
    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return result;
    }
};


/*
 题目描述
二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，
对于存储在下标 N 的节点，它的左子节点和右子节点分存储在下标 2*N 和 2*N+1，
并且我们用值 -1 代表一个节点为空。
给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。

输入描述
输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。
注意第一个元素即为根节点的值，即数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略了。
输入的树最多为7层。

输出描述
输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个

输入
3 5 7 -1 -1 2 4
输出
3 7 2

输入
5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
输出
5 8 7 6

 */

class Solution03
{
public:
    int curr_min = INT_MAX;
    vector<int>result;
    struct TreeNode
    {
        int val, index;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val, int index) :val(val), index(index) {};
    };
    void reviewTree(TreeNode* root)
    {
        queue<vector<int>>path_queue;
        queue<TreeNode*>node_queue;

        vector<int>root_vec = { root->val };
        path_queue.push(root_vec);
        node_queue.push(root);

        while (!node_queue.empty())
        {
            TreeNode* node = node_queue.front();
            node_queue.pop();
            vector<int>node_vec = path_queue.front();
            path_queue.pop();

            if (node->left==nullptr&&node->right==nullptr)
            {
                //叶子节点
                if (node->val < curr_min)
                {
                    curr_min = node->val;
                    result = node_vec;
                }
            }

            if (node->left!=nullptr)
            {
                vector<int>new_vec = node_vec;
                new_vec.push_back(node->left->val);
                node_queue.push(node->left);
                path_queue.push(new_vec);
            }

            if (node->right!=nullptr)
            {
                vector<int>new_vec = node_vec;
                new_vec.push_back(node->right->val);
                node_queue.push(node->right);
                path_queue.push(new_vec);
            }

        }

        //reviewTree
    }
    TreeNode* buildNode(vector<int>&tree_vec)
    {
        int vec_size = tree_vec.size();
        TreeNode* root = new TreeNode(tree_vec[0], 0);

        queue<TreeNode*>bfs_queue;
        bfs_queue.push(root);
        while (!bfs_queue.empty())
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();
            int node_index = top_node->index;

            if (2*node_index+1 < vec_size && tree_vec[2 * node_index + 1]!=-1)
            {
                int left_val = tree_vec[2 * node_index + 1];
                TreeNode* left_node = new TreeNode(left_val, 2 * node_index + 1);
                top_node->left = left_node;
                bfs_queue.push(left_node);
            }
            if (2 * node_index + 2 < vec_size && tree_vec[2 * node_index + 2] != -1)
            {
                int right_val = tree_vec[2 * node_index + 2];
                TreeNode* right_node = new TreeNode(right_val, 2 * node_index + 2);
                top_node->right = right_node;
                bfs_queue.push(right_node);
            }

        }
        return root;
    }

    void solve03(vector<int>& tree_vec)
    {
        TreeNode* root = buildNode(tree_vec);
        reviewTree(root);

        //cout << result.size();
        for (auto&num:result)
        {
            cout << num << ' ';
        }

    }

};

/*
 给定一个以顺序储存结构存储整数值的完全二叉树序列（最多1000个整数），
 请找出此完全二叉树的所有非叶子节点部分，然后采用后序遍历方式将此部分树（不包含叶子）输出。
1、只有一个节点的树，此节点认定为根节点（非叶子）。
2、此完全二叉树并非满二叉树，可能存在倒数第二层出现叶子或者无右叶子的情况
其他说明：二叉树的后序遍历是基于根来说的，遍历顺序为：左-右-根
 */
class Solution04
{
public:
    struct TreeNode
    {
        int val, index;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val,int index) :val(val),index(index) {};
    };
    vector<int>result;
    void postOrder(TreeNode* node)
    {
        if (node == nullptr)
            return;

        postOrder(node->left);
        postOrder(node->right);
        if (node->left!=nullptr||node->right!=nullptr)
        {
            result.push_back(node->val);
        }
    }

    TreeNode* buildTree(vector<int>&tree_vec)
    {
        int vec_size = tree_vec.size();
        TreeNode* root = new TreeNode(tree_vec[0], 0);
        queue<TreeNode*>bfs_queue;
        bfs_queue.push(root);

        while (!bfs_queue.empty())
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();
            int node_index = top_node->index;

            if (2*node_index+1< vec_size)
            {
                int left_val = tree_vec[2 * node_index + 1];
                int left_index = 2 * node_index + 1;
                TreeNode* left_node = new TreeNode(left_val, left_index);
                top_node->left = left_node;
                bfs_queue.push(left_node);
            }

            if (2*node_index+2 < vec_size)
            {
                int right_val = tree_vec[2 * node_index + 2];
                int right_index = 2 * node_index + 2;
                TreeNode* right_node = new TreeNode(right_val, right_index);
                top_node->right = right_node;
                bfs_queue.push(right_node);
            }

        }
        return root;

    }

    void solve04(vector<int>& tree_vec)
    {
        if (tree_vec.size()==1)
        {
            cout << tree_vec[0];
            return;
        }

        TreeNode* root = buildTree(tree_vec);

        postOrder(root);
        for (auto&num:result)
        {
            cout << num << ' ';
        }
    }
};

/*
给定一个二叉树，每个节点上站着一个人，
节点数字表示父节点到该节点传递悄悄话需要花费的时间。
初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，
求二叉树所有节点上的人都接收到悄悄话花费的时间。

输入描述
给定一个数组表示二叉树，-1 表示空节点
输出描述
返回所有节点都接收到悄悄话花费的时间

输入
0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
输出
38
 */
class Solution05
{
public:
    struct TreeNode
    {
        int val, index;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val, int index) :val(val), index(index) {};
    };
    vector<int>result_vec;
    int result = 0;
    void reviewTree(TreeNode* root)
    {
        queue<vector<int>>path_queue;
        queue<TreeNode*>node_queue;

        vector<int>root_vec = { root->val };
        path_queue.push(root_vec);
        node_queue.push(root);

        while (!node_queue.empty())
        {
            int q_size = node_queue.size();
            for (int i=0;i<q_size;i++)
            {
                TreeNode* top_node = node_queue.front();
                node_queue.pop();
                vector<int>node_vec = path_queue.front();
                path_queue.pop();

                if (top_node->left == nullptr && top_node->right == nullptr)
                {
                    int sum = 0;
                    for (auto&num:node_vec)
                    {
                        sum += num;
                    }
                    result = max(result, sum);
                }

                if (top_node->left != nullptr)
                {
                    vector<int>new_vec = node_vec;
                    new_vec.push_back(top_node->left->val);
                    path_queue.push(new_vec);
                    node_queue.push(top_node->left);
                }

                if (top_node->right != nullptr)
                {
                    vector<int>new_vec = node_vec;
                    new_vec.push_back(top_node->right->val);
                    path_queue.push(new_vec);
                    node_queue.push(top_node->right);
                }
            }

        }
	    
    }
    TreeNode* buildTree(vector<int>&tree_vec)
    {
        int vec_size = tree_vec.size();
        TreeNode* root = new TreeNode(tree_vec[0], 0);
        queue<TreeNode*>bfs_queue;
        bfs_queue.push(root);
        while (!bfs_queue.empty())
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();
            int node_index = top_node->index;
            //2*i+1
            if (2*node_index+1<vec_size && tree_vec[2 * node_index + 1]!=-1)
            {
                int left_val = tree_vec[2 * node_index + 1];
                int left_index = 2 * node_index + 1;
                TreeNode* left_node = new TreeNode(left_val, left_index);
                top_node->left = left_node;
                bfs_queue.push(left_node);
            }
			//2*i+2
            if (2 * node_index + 2 < vec_size && tree_vec[2 * node_index + 2] != -1)
            {
                int right_val = tree_vec[2 * node_index + 2];
                int right_index = 2 * node_index + 2;
                TreeNode* right_node = new TreeNode(right_val, right_index);
                top_node->right = right_node;
                bfs_queue.push(right_node);
            }
        }
        return root;
    }

    void solve05(vector<int>& tree_vec)
    {
        TreeNode* root = buildTree(tree_vec);
        reviewTree(root);

        cout << result;
    }
};

int main()
{
	{
        //0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
        vector<int>tree_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            tree_vec.push_back(stoi(token));
        }
        //for (auto&num:tree_vec)
        //{
        //    cout << num << ',';
        //}
        //0,9,20,-1,-1,15,7,-1,-1,-1,-1,3,2
        //vector<int>tree_vec = { 0,9,20,-1,-1,15,7,-1,-1,-1,-1,3,2 };
        Solution05 solu;
        solu.solve05(tree_vec);

        return 0;
	}
	{
        //1 2 3 4 5 6 7
        //2 3 1
        //vector<int>tree_vec = { 1,2,3,4,5,6,7 };
        vector<int>tree_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            tree_vec.push_back(stoi(token));
        }

        Solution04 solu;
        solu.solve04(tree_vec);

        return 0;
	}
	{
        //3 5 7 -1 -1 2 4
        vector<int>tree_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            tree_vec.push_back(stoi(token));
        }

        //vector<int>tree_vec = { 3,5,7,-1,-1,2,4 };
        Solution03 solu;
        solu.solve03(tree_vec);


        return 0;
	}

	{
        //root = [1,2,3]
        //root = [-10,9,20,null,null,15,7]
        const int null = INT_MIN;
        vector<int>tree_vec = { -10,9,20,null,null,15,7 };
        TreeNode* node = BuildNode(tree_vec);
        Solution02 solu;
        cout << solu.maxPathSum(node);

        return 0;
	}
/*
输入：root = [5,4,5,1,1,5]
输出：2
 */
    vector<int>tree_vec = { 5,4,5,1,1,5 };
    TreeNode* root = BuildNode(tree_vec);
    Solution01 solu;
    cout << solu.longestUnivaluePath(root);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
